﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace ns
{

    public class TestDemo
    {
        private int Buy(int a, int b, int c)
        {
            int m, n;
            m = n = a / b; //表示能买N瓶水
            while (m >= c) //n个瓶盖 》 c个瓶盖
            {
                n += m / c; //瓶盖能换N瓶水
                m = (m / c) + (m % c); //换的N瓶水+剩余的瓶盖
            }
            return n;
        }


        //144.二叉树前序遍历：递归方式
        public IList<int> PreorderTraversal_1(TreeNode root)
        {
            IList<int> list = new List<int>();
            if (root == null) return list;
            Preorder(root, list);
            return list;
        }

        private void Preorder(TreeNode root, IList<int> list)
        {
            list.Add(root.val);
            if (root.left != null) Preorder(root.left, list);
            if (root.right != null) Preorder(root.right, list);
        }

        //144.二叉树前序遍历：迭代方式
        public IList<int> PreorderTraversal_2(TreeNode root)
        {
            IList<int> list = new List<int>();
            if (root == null) return list;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode curNode = root; //当前节点
            while (stack.Count != 0 || curNode != null)
            {
                while (curNode != null)
                {
                    list.Add(curNode.val);
                    stack.Push(curNode); //压入栈
                    curNode = curNode.left;
                }
                //当前为左节点为空节点
                curNode = stack.Pop(); //把上一个根节点压出栈
                curNode = curNode.right; //获取右节点
            }
            return list;
        }


        //94. 二叉树的中序遍历：递归算法
        public IList<int> InorderTraversal_1(TreeNode root)
        {
            IList<int> list = new List<int>();
            Inorder(root, list);
            return list;
        }

        private void Inorder(TreeNode root, IList<int> list)
        {
            if (root == null) return; //空节点直接返回
            Inorder(root.left, list);
            list.Add(root.val);
            Inorder(root.right, list);
        }

        //94. 二叉树的中序遍历：迭代算法
        public IList<int> InorderTraversal_2(TreeNode root)
        {
            IList<int> list = new List<int>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode curNode = root;
            while (stack.Any() || curNode != null)
            {
                while (curNode != null)
                {
                    stack.Push(curNode); //压入栈
                    curNode = curNode.left; //左节点
                }
                root = stack.Pop();
                list.Add(root.val); //出栈第一个
                curNode = root.right; //右节点,会报错
            }
            return list;
        }

        //145. 二叉树的后序遍历 ：递归
        public IList<int> PostorderTraversal_1(TreeNode root)
        {
            IList<int> list = new List<int>();
            Postorder(root, list);
            return list;
        }

        private void Postorder(TreeNode root, IList<int> list)
        {
            if (root == null) return; //空节点直接返回
            Postorder(root.left, list);
            Postorder(root.right, list);
            list.Add(root.val);
        }

        //145. 二叉树的后序遍历 ：迭代
        public IList<int> PostorderTraversal_2(TreeNode root)
        {
            IList<int> list = new List<int>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode curNode = root;
            TreeNode preNode = null; //代表此刻左节点
            while (stack.Any() || curNode != null)
            {
                while (curNode != null)
                {
                    stack.Push(curNode);
                    curNode = curNode.left; //判断还有没有左节点
                }
                curNode = stack.Pop(); //此节点没有左节点或者节点置空了，压出上一个赋值
                if (curNode.right == null || curNode.right == preNode) //当前没有右节点，右节点为null
                {
                    list.Add(curNode.val); //把节点添加list
                    preNode = curNode; //把当前节点给preNode
                    curNode = null; //当前根节点置空
                }
                else //当前有右节点，不为空，更节点再次入栈
                {
                    stack.Push(curNode); //重新入栈
                    curNode = curNode.right;
                }
            }
            return list;
        }

    }

    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}